package 数组;

/**
 * 力扣：209
 * @Author zxl
 * @Date 2022/1/2 10:42
 * @Desc 在一个正整数数组nums中找到最小长度的连续子数组，使子数组元素之和大于或等于s，
 *         返回满足条件的连续子数组的最小长度，如果没有找到返回0
 */
public class 长度最小的子数组 {

    public static void main(String[] args) {
        int[] nums = {4,6,2,4,9,8,7};
        System.out.println("最小长度：" + minLengthByWindow2(nums,22));
    }

    /**
     * 滑动窗口
     * 窗口滑动：如果当前窗口的值大于s，则移动窗口起始位置，尝试缩小窗口，
     *              如果缩小一次后的窗口值不大于s，则窗口结束位置右移，扩大窗口
     * @param nums
     * @param s
     * @return
     */
    public static int minLengthByWindow2(int[] nums,int s){
        int minlength = Integer.MAX_VALUE;
        int lastIndex = 0;
        int sum = 0;
        for (int preIndex = 0;preIndex<nums.length;preIndex++){
            sum += nums[preIndex];
            while (sum >= s){
                int arrayLength = preIndex - lastIndex + 1;
                if (arrayLength < minlength){
                    minlength = arrayLength;
                }
                // 窗口移动
                sum -= nums[lastIndex];
                lastIndex ++;
            }
        }
        if (minlength == Integer.MAX_VALUE){
            return 0;
        }
        return minlength;
    }

    /**
     * 滑动窗口
     * 窗口移动：起始位置移动+1，结束位置重置为起始位置-1，相当于窗口大小每次都从1开始扩大
     * @param nums
     * @param s
     * @return
     */
    public static int minLengthByWindow(int[] nums,int s){
        int minlength = Integer.MAX_VALUE;
        int lastIndex = 0;
        int sum = 0;
        for (int preIndex = 0;preIndex < nums.length ; preIndex++){
            sum += nums[preIndex];
            if (sum >= s){
                int arrayLength = preIndex - lastIndex + 1;
                if (arrayLength < minlength){
                    minlength = arrayLength;
                }
                // 窗口移动
                lastIndex ++;
                preIndex = lastIndex-1;
                sum = 0;
            }
        }
        if (minlength == Integer.MAX_VALUE){
            return 0;
        }
        return minlength;
    }

    /**
     * 双循环暴力破解，时间复杂度O(n^2)
     * @param nums
     * @param s
     * @return
     */
    public static int minLength(int[] nums,int s){
        int res = Integer.MAX_VALUE;
        for (int i = 0; i < nums.length; i++) {
            int sum = 0;
            for (int j = i; j < nums.length; j++){
                sum += nums[j];
                if (sum >= s){
                    if ((j - i+ 1) < res){
                        res = j-i+1;
                    }
                    break;
                }
            }
        }
        if (res == Integer.MAX_VALUE){
            return 0;
        }
        return res;
    }

}
